package leetcode;

import java.util.HashMap;

/**
 * Created by Ghost on 2014/11/3 0003.
 */
public class Longest_Consecutive_Sequence {
    public int longestConsecutive(int[] num) {
        HashMap<Integer,Boolean> map = new HashMap<Integer, Boolean>(num.length);
        for(int i=0;i<num.length;i++){
            map.put(num[i],false);
        }
        int max = 0;
        for(int i=0;i<num.length;i++){
            int len = 0;
            if(!map.get(num[i])){
                len++;
                map.put(num[i],true);
                int j = num[i]-1;
                while(map.containsKey(j) && !map.get(j)){
                    len++;
                    map.put(j,true);
                    j--;

                }

                j = num[i]+1;
                while(map.containsKey(j) && !map.get(j)){
                    len++;
                    map.put(j,true);
                    j++;
                }

                max = max>len?max:len;
            }
        }
        return max;
    }
    public static void main(String[] args){
        Longest_Consecutive_Sequence longest_consecutive_sequence = new Longest_Consecutive_Sequence();
        int[] num = {100,4,200,1,3,2};
        System.out.println(longest_consecutive_sequence.longestConsecutive(num));
    }
}
